package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Day20_1 {
    /***
     * 递归 前序
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        preErgodic(root, res);
        return res;
    }

    /**
     * 根->左->右
     *
     * @param nowNode
     * @param res
     */
    public static void preErgodic(TreeNode nowNode, List<Integer> res) {
        if (nowNode != null) {
            res.add(nowNode.val);
            preErgodic(nowNode.left, res);
            preErgodic(nowNode.right, res);
        }
    }


    public static List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        //模拟栈
        LinkedList<TreeNode> preErgodicHelp = new LinkedList<>();
        TreeNode temp = root;
        //temp 不为空 preErgodicHelp数量一直增加 意味着一直在向左
        //preErgodicHelp不为空temp不为空代表，遍历左节点还没有结束，一直向左走
        //preErgodicHelp不为空temp为空代表，没有左节点了，我们需要返回上一层的节点遍历他的右节点
        while (temp != null || !preErgodicHelp.isEmpty()) {
            while (temp != null) {
                res.add(temp.val);
                //当前层级的节点
                preErgodicHelp.addFirst(temp);
                //向左
                temp = temp.left;
            }
            //返回上一层
            temp = preErgodicHelp.pop();
            //向右
            temp = temp.right;
        }
        return res;
    }


}
